package com.lw.leetcode.dp.a;

/**
 * Created with IntelliJ IDEA.
 * 338. 比特位计数
 * 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/23 11:36
 */
public class CountBits {
    public int[] countBits(int num) {
        int[] arr = new int[num + 1];
        arr[0] = 0;
        if (num == 0) {
            return arr;
        }
        arr[1] = 1;
        if (num == 1) {
            return arr;
        }
        arr[2] = 1;
        if (num == 2) {
            return arr;
        }
        arr[3] = 2;
        if (num == 3) {
            return arr;
        }
        int m = (num - 1) / 2;
        int index = 0;
        for (int i = 2; i <= m; i++) {
            index = i << 1;
            arr[index] = arr[i];
            arr[index + 1] = arr[i] + 1;
        }
        if (index + 1 < num) {
            arr[num] = arr[num >> 1];
        }
        return arr;
    }
}
